package com.yun.algorithm.sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/*
    数据量范围用基数排序
 */
public class E01leetcode1122 {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int v2 : arr2) {
            map.put(v2, 0);
        }
        for (int i = 0; i < arr1.length; i++) {
            int v1=arr1[i];
            if (map.containsKey(v1)) {
                map.put(v1, map.get(v1) + 1);
                arr1[i]=0;
            }
        }
        quickSort(arr1);
        int k=0;
        for (int v2 : arr2) {
            int cnt=map.get(v2);
            for (int i = 0; i < cnt; i++) {
                arr1[k]=v2;
                k++;
            }
        }
        return arr1;
    }

    private void quickSort(int[] a) {
        quick(a, 0, a.length - 1);
    }

    private void quick(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(a, left, right);
        quick(a, left, p - 1);
        quick(a, p+1, right);
    }

    private int partition(int[] a, int left, int right) {
        int pv = a[right];
        int i = left;
        int j = left;
        while (j < right) {
            if (a[j] < pv) {
                if (i != j) {
                    swap(a, i, j);
                }
                i++;
            }
            j++;
        }
        swap(a,i,right);
        return i;
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] arr1=new int[]{2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2=new int[]{2,1,4,3,9,6};
        int[] res=new E01leetcode1122().relativeSortArray(arr1,arr2);
        System.out.println(Arrays.toString(res));
    }
}
